package offerbook;

import utils.TreeNode;
import utils.TreeUtil;

/**
 * @date 2019/11/11 0011 下午 12:03
 * 给定一棵二叉搜索树，请找出其中的第k小的结点。
 * 例如，（5，3，7，2，4，6，8）中,
 * 按结点数值大小顺序第三小结点的值为4。
 *
* 那么中序遍历即可。顺序的。
 *
 */
public class Code63_TheK_NodeOfBST {


    /**
     * 二叉搜索树
     */
    static int sum = 0;
    static TreeNode KthNodeBST(TreeNode pRoot, int k) {
        if(pRoot == null || k <=0){
            return null;
        }
        sum = k;
        return InOrder(pRoot);

    }

    private static TreeNode InOrder(TreeNode pRoot) {
        TreeNode treeNode = null ;
        if(pRoot.left != null)
            treeNode = InOrder(pRoot.left);
        if(--sum == 0) {
            return pRoot;
        }
        //注意这里要判断sum>0，否则 sum = 0也进入，会错误
        if(pRoot.right != null && sum > 0)
            treeNode = InOrder(pRoot.right);
        return treeNode;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        TreeUtil.printTree(treeNode);
        System.out.println(KthNodeBST(treeNode, 3).val);
    }

}
